Multiple-separation color imaging devices, such as color laser printers, copiers and offset printers, operate by transferring several image separations to a printing medium, such as paper, in stages. Each image separation is printed with a different colorant, such as ink or toner. For example, a four-color printer typically applies cyan (C), magenta (M), yellow (Y), and black (K) image separations during separate stages. These image separations can be created using a single drum for four-pass printers, or on four drums for in-line printers. The image separations can be transferred to an intermediate drum or belt, and then to the medium, or directly to the medium in four transfers.
Because the multiple image separations are created in separate mechanical steps, it is difficult to perfectly align the separations so that no gaps appear at edges between adjacent colors. Even very small gaps can form visible white lines in the printed image. Mechanical alignment of the image planes can reduce registration errors, but cannot completely eliminate such errors. Various techniques have been used to compensate for registration errors in multiple separation color imaging devices. Trapping is one such technique in which color areas in an image are intentionally overlapped so that small registration errors do not create visible gaps.
Previously known raster-based trapping techniques operate on images that have been first scanned or converted from a page description language to a sequence of high resolution scan lines, each line containing individual picture elements (“pixels”). Each pixel in each raster line is processed in sequence, and one or more adjacent pixels are compared to determine color boundaries. In particular, previously-known trapping processes typically perform the following steps: (1) identify edges in the image; (2) determine for each pair of colors on either side of the edge (a) whether trapping should be performed, (b) the color that should be used for the trapped pixels, and (c) where the color should be placed; and (3) modify the image accordingly.
In general, previously known raster-based trapping techniques utilize a “push” method, in which colorant value modifications are pushed from a trapping edge to many neighboring pixels along the edge. Referring to FIG. 1, an example of such a previously known push trapping technique is described. As shown in FIG. 1A, bitmap array 10 represents a segment of a composite image that includes multiple color separations. In particular, array 10 includes eleven rows and thirteen columns of pixels 12. Each pixel 12 has a corresponding color, comprised of a combination of the colorants used to depict the image. For example, in a CMYK printing process, each pixel 12 has a corresponding color that may be expressed as a combination of C, M, Y and K colorants. Array 10 includes pixels 12a having color D (corresponding to colorants CD, MD, YD and KD) and pixels 12b having color E (corresponding to colorants CE, ME, YE and KE). Edge 14 is formed at the border between pixels 12a and pixels 12b. 
As shown in FIG. 1B, in conventional push trapping techniques, trapping zones 16 (above) and 18 (below) edge 14 are identified. The size of the trapping zones typically is determined based on measurements of misregistration on a specific imaging device. In the example shown in FIG. 1B, trapping zones 16 and 18 each have a trapping width of two pixels. After the trapping zones are identified, a decision is made whether to trap pixels in either or both of the trapping zones. Such a decision typically is based on a variety of factors, including the component colorant values of colors D and E, and differences between the component colorant values. In FIG. 1B, pixels 12c in trap zone 18 are trapped. In particular, all pixels 12c in trap zone 18 have their color E replaced by color E′.
A disadvantage of such previously known push trapping techniques is that they are computationally inefficient to implement in hardware image processing circuitry. In particular, such previously known techniques typically require that the pixel data are first processed to identify edges between adjacent regions, and then reprocessed to push trap colors in one or both directions perpendicular to each identified edge. If the image includes a large array of pixels (e.g., a letter size image at a resolution of 1,200 dots per inch may include more than 134 million pixels), such previously known trapping techniques may take a considerable amount of time to process.
In view of the foregoing, it would be desirable to provide methods and apparatus to efficiently trap digital color images.
It further would be desirable to provide methods and apparatus that allow multiple trapping operations to be performed in parallel.
It also would be desirable to provide methods and apparatus for trapping that may be efficiently implemented in hardware image processing circuitry.